1. Field of the Invention
This invention generally relates to video motion or displacement estimation and video processing, and more specifically to a system and method for matching blocks in a sequence of images.
2. Description of the Related Art
Image or video encoding is widely used in the cable, interenet, computer, CD ROM, video-conferencing, and other industries. Common image or video coding schemes (e.g., the Motion Picture Expert Group (MPEG) image coding scheme) define blocks of pixels in an image for coding and motion estimation purposes (e.g., typically blocks of 16 by 16 or 8 by 8 pixels are used in the coding process). In a video comprising a sequence of images or frames, motion or displacement of a block in one frame to a similar block in the next frame is used to reduce the encoded video storage space and decrease the time required to transmit the video over a fixed bandwidth medium. Using such a scheme, each block of an initial frame is encoded, then the displacement (if any) of each block in subsequent frames is determined and encoded (e.g., in a vector) along with its residual (i.e., original block minus predicted value). Decoding comprises decoding the initial frame, and simply adding the displacement residual of each block to create each subsequent frame in the video.
Key to the block motion or displacement estimation method is the matching of a specific block (i.e., group of pixels) from one frame to the same or similar block (i.e., group of pixels) in the next frame in order to determine the relative displacement of the block.
Conventional methods match blocks in each frame by using a measurement of intensity and/or contrast of the blocks from one frame to the next (e.g., two blocks in two sequential frames having the same intensity are likely to be matching blocks). Conventional methods do not use information about the types of pixels in the block or otherwise utilize qualitative characteristics or information about the content of the block itself for matching purposes. Conventional methods have proven useful in some simple video applications such as slow-moving video, or low-resolution video. However, conventional techniques often grossly mismatch blocks in more difficult or "problem" videos such as fast-moving video (e.g., a basketball game). The decoded images sometimes appear blocked, granular, and/or fuzzy and are generally poor quality.
It would be beneficial to increase the accuracy of matching blocks in sequential frames of a video stream, and thus improve the encoding process, storage space, encoding time, and final video quality. In addition, it would be beneficial to have an accurate block matching method for various pre-processing enhancements of video images.